\documentclass{article}[11pt]
\usepackage{xspace,colortbl}
\usepackage{amsmath}
\usepackage{color}
\title{Proposal of Undergraduate Thesis - A Survey of the Game "Lights Out!"}
\author{Jiajin Yu}
\begin{document}
\maketitle
\section{Aim}
Through this survey, we are going to demonstrate different approaches to solve
the game "Lights Out!" or more formally \emph{the parity dominating set
problem}. We are also going to devise a single framework so that different
methods can be combined together.
\section{Meaning}
From the study of the game "Lights Out!", common skills used in solving
combinatory games can be learned. Specifically, we can understand how different
fields solve the parity dominating set problem by using theorems in their own
fields, which gives an illumination of the usage of common techniques for
solving problems in different fields.
\section{Current Status of the Research}
It was K.Sunter who first proved that each graph has an odd parity dominating
set. Then different approaches are used to simplify the proof and get parity
dominating set of small size. One common method is to use the Fibonacci
polynomial to obtain the parity dominating set smaller than the normal Gauss
elimination method.
\section{Content of the Research and Thesis}
{\color{blue} The game "Light Out!" is played on a $5\times5$ grid of buttons
which also have lights in them. By pressing a button, its light and its
rectilinear neighbors will change(switch \texttt{ON} if it was \texttt{OFF},
and vice versa). Give some initial pattern of lights, one has to switch them
all \texttt{OFF} by pressing several buttons and we call this pattern
\emph{solvable} if we can turn all of lights off. Obviously, the game can}
{\color{blue}naturally generalizes to any graph $G$. We can propose problems to
this game such as
\begin{enumerate}
\item
Are all the graphs with the initial state all \texttt{ON} solvable?
\item
Is arbitrary pattern on any graph solvable?
\item
How can we tell the minimal times of press if some pattern is solvable? Does
this belongs to $\mathcal{NPC}$?
\end{enumerate}
 }

The survey should first demonstrate methods from different field(cellular
automata, graph theory, etc.). Then links between them will be given. After
that, a unified framework will be established to include those different
approaches. Particularly, we can use the unified framework to explain the
result gotten from different approaches. At last, we are going to propose open
problems related to the topic.
\section{Scheme}
In order to get a comprehensive and accurate survey, it is important that most
of the important paper related to the topic should be browsed. Those which
develop the key idea should be studied carefully. Then a scratch is needed. The
scratch version should be discussed with the supervisor to make sure the
development of main idea is acceptable. Then the actual writing starts. When
the writing is over, the paper should be carefully reviewed and refined. After
the refinement of the survey, if time is available, some presentation materials
should also be prepared.

{\color{blue}Regarding to the detail, at first, we are going to study how
K.Sunter proved the existence of odd parity dominating set in every graph by
cellular automata and how can we simplify the proof by introducing the linear
algebra over $GF(2)$. Then, we are going to study properties of matrix
constructed by the $GF(2)$ to represent the graph and activations on it. After
that, we are going to understand the basic Gauss elimination method and the
algorithm to do Gauss elimination on the graph. We are also going to understand
the relationship of Fibonacci polynomials with the binary matrix and properties
of the Fibonacci polynomials.}
\section{Prospective Result}
The prospective result is a comprehensive survey about the topic. The survey
should use a unified framework to include different approaches to solve the
game. If possible, some open problem of this topic will also be resolved.
\end{document}
